package trie

import (
	"fmt"
)

type Trie struct {
	root *TreeNode
}

func (this Trie) string() {

	p := this.root

	fmt.Println(string(p.char))

	print(*p)
}

func print(p TreeNode) {

	for _, treeNode := range p.children {

		if treeNode != nil {
			fmt.Print(string(treeNode.char), " ")
			print(*treeNode)
		}

	}

	fmt.Println()

	if p.children == nil {

		return
	}
}

func (this *Trie) find(pattern string) bool {

	chars := []rune(pattern)
	p := this.root

	for i := 0; i < len(chars); i++ {

		index := chars[i] - 'a'

		if p.children[index] == nil {
			return false

		}

		p = p.children[index]
	}

	if !p.isEnding {
		return false
	}

	return true
}

func (this *Trie) prefixMatch(pattern string) (res *[] string) {

	chars := []rune(pattern)
	p := this.root
	res = new([]string)

	for i := 0; i < len(chars); i++ {
		index := chars[i] - 'a'
		if p.children[index] == nil {
			return res
		}
		p = p.children[index]
	}

	findText2(p, pattern, res)

	return res
}

func findText2(p *TreeNode, str string, res *[]string) {
	if p != nil {
		for _, node := range p.children {

			if node != nil {
				srr2 := fmt.Sprintf("%s%c", str, node.char)
				if node.isEnding {
					*res = append(*res, srr2)
				}
				findText2(node, srr2, res)
			}

		}
	}
}

func (this *Trie) insert(str string) {

	chars := []rune(str)

	p := this.root

	for i := 0; i < len(chars); i++ {

		index := chars[i] - 'a'

		if p.children[index] == nil {
			p.children[index] = &TreeNode{char: chars[i], isEnding: false, children: make([]*TreeNode, 26)}
		}

		p = p.children[index]
	}
	p.isEnding = true
}

type TreeNode struct {
	char     rune
	children []*TreeNode
	isEnding bool
}
